//度限制生成树
//degree_bounded_spanning_tree.cpp

//在构造最小生成树时，图中一个指定的节点有度的限制
//指定某节点v0，它在生成树中的度数为k，它在生成树中必须有k条边，即degree(v0) = k
//这样被指定的度限制节点只有一个，当为多个时，本问题成为一个NP完全问题

//无解情况：
//在无向简单图G中，当将指定节点v0及其边去掉，剩下的图被分成m个图，即m个连通分量
//当k < m时，肯定不存在k度限制最小生成树，即无解情况
//
//有解情况：
//在图G中，先将v0点及其边排除在外，得到剩余图的m个连通分量
//构造每个连通分量的最小生成树，记录每个连通分量的生成树的权值和weight
//然后从v0向每个连通分量添加一条边(选择权值最小的边)，共m条边(m <= k)
//这样就得到了m度限制生成树
//
//1)原始思路：
//若m < k，则还需要向v0添加 k-m 条边，对v0的剩余边按权值从小到大进行如下操作：
//对v0剩余的每条边e，添加入一个连通分量的生成树中
//此边一会让该生成树形成环，找出环中权值最大的边并删除
//可以得到一个新的生成树权值和weight，若新替换的边使生成树权值减少，则枚举下一条边
//若这条新替换的边不使生成树权值和减少，则跳过这条边
//这样添加 k-m 条边，则v0度数为k，即可得到v0节点的k度限制生成树
//缺点是每考虑一条边，就要枚举这条边的环上的所有边，找出权值最大的边，时间复杂度较高
//
//2)优化方法：用动态规划方法求环中权值最大的边
//和次小生成树中的方法一样用bfs和动态规划的方法构造一个max_edge表
//得到图中任意两点之间，在最小生成树的路径上的权值最大的边

//void degree_bounded_spanning_tree(edge_list& e, int n, int beg, int k)
